package com.jp.algorithm.binaryIndexTree;

public class BinaryIndexTree {
    int[] a;
    int[] c;
    public  BinaryIndexTree(int[] array){

        a=new int[array.length];
        for(int i=1;i<array.length;i++){
            a[i]=array[i];
        }

        c=new int[a.length];
        for(int i=1;i<c.length;i++){
            c[i]=0;
        }

        init();
    }


    private void  init(){
        int[] pre = new int[a.length];
        for(int i=0;i<pre.length;i++){
            pre[i]=0;
        }

        for(int i=1;i<c.length;i++){
            pre[i]=pre[i-1]+a[i];
            c[i]=pre[i]-pre[i-lowbit(i)];
        }
    }
    public void print(){
        for(int i=1;i<c.length;i++){
            System.out.println(c[i]);
        }
    }

    private int getSum(int i){
        int sum=a[i];
        for(int tmp=i-1; tmp>0; tmp-=lowbit(tmp)){
            sum+=c[tmp];
        }
        return sum;
    }

    public void update(int x,int value){
        int dif=value-a[x];
        a[x]=value;
        for(int i=x;i<c.length;i+=lowbit(i)){
            c[i]+=dif;
        }
    }


    private int lowbit(int x) {
        return x&(-x);
    }

    public static  void testInit(){
        int[] array={0,1,2,3,4,5,6,7,8};
        BinaryIndexTree binaryIndexTree=new BinaryIndexTree(array);
        binaryIndexTree.print();
    }
    public static  void testGetSum(){
        int[] array={0,1,2,3,4,5,6,7,8};
        BinaryIndexTree binaryIndexTree=new BinaryIndexTree(array);
        System.out.println(binaryIndexTree.getSum(4));
    }
    public static void testUpdate(){
        int[] array={0,1,2,3,4,5,6,7,8};
        BinaryIndexTree binaryIndexTree=new BinaryIndexTree(array);
        binaryIndexTree.update(1,2);
        binaryIndexTree.print();
    }


    public static void main(String[] args) {
        //testInit();
        //testGetSum();
        testUpdate();
    }

}
